/* 

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
 

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// DFS
// 题解：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/shou-hua-tu-jie-fen-ge-deng-he-zi-ji-dfshui-su-si-/
/**
 * @param {number[]} nums
 * @return {boolean}
 */
let canPartition = (nums) => {
    let sum = 0;
    for (let n of nums) { // 求数组和
        sum += n;
    }
    if (sum % 2 != 0) return false; // 如果 sum 为奇数，直接返回 false
    let memo = new Map();
    let target = sum / 2; // 目标和

    let dfs = (curSum, i) => { // curSum是当前累加和，i是指针
        if (i == nums.length || curSum > target) { // 递归的出口
            return false;
        }
        if (curSum == target) { // 递归的出口
            return true;
        }
        let key = curSum + '&' + i; // 描述一个问题的key
        if (memo.has(key)) { // 如果memo中有对应的缓存值，直接使用
            return memo.get(key);
        }
        let res = dfs(curSum + nums[i], i + 1) || dfs(curSum, i + 1);
        memo.set(key, res); // 计算的结果存入memo
        return res;
    };

    return dfs(0, 0); // 递归的入口，当前和为0，指针为0
};